import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution_102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        queue.add(root);
        queue1.add(root);
        while (!queue1.isEmpty()) {
            // 复制 queue1 到 queue
            copyList(queue1, queue);
            List<Integer> resItem = new ArrayList<>();
            while(!queue.isEmpty()) {
                TreeNode item = queue.poll();
                resItem.add(item.val);
                if (item.left != null) { queue1.add(item.left); }
                if (item.right != null) { queue1.add(item.right); }
            }
            res.add(resItem);
        }
        return res;
    }

    public Queue<TreeNode> copyList(Queue<TreeNode> from, Queue<TreeNode> to) {
        if (!to.isEmpty()) {to = new LinkedList<>();}
        while (!from.isEmpty()) {
            to.add(from.poll());
        }
        return to;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        List<List<Integer>> list = new Solution_102().levelOrder(root);
        System.out.println(list);
    }
}
